In a satellite-based positioning (SPS) system, each satellite has a unique code that it transmits. For example, a GPS satellite continuously transmits a unique pseudorandom sequence of bits known as a C/A code every millisecond. A GPS receiver has a copy of the appropriate C/A code and can thus correlate its C/A code copy with the received satellite signal. Since the C/A code is used for positioning instead of data transfer, it is conventional to refer to its bits as “chips.” In a GPS system, a satellite transmits 1023 chips every millisecond. The GPS receiver correlates the received chips with its C/A code copy. Note that there is a constellation of GPS satellites so it would be very inefficient to correlate for each satellite since only a subset of the constellation will be visible at any given time. The GPS receiver uses almanac data to identify the satellites from which it should be receiving chips. In this fashion, a GPS receiver upon cold start does not need to correlate for each satellite but only for the likely candidates.
To obtain a position fix, a conventional SPS receiver such as a GPS receiver correlates its copy of the C/A code for the satellite it is searching for with the received signal. Since the noise is incoherent to the sequence of chips, this correlation has the advantageous property that the noise is decorrelated whereas the satellite signal is correlated. In this fashion, satellite signals are “pulled” out of the noise despite the satellites being thousands of miles away and having relatively weak transmitters. In a GPS system, the correlation will have a sharp peak every 1023 chips since the satellite's C/A code sequence is 1023 chips in length. The GPS receiver can thus identify the time of receipt for a C/A code sequence based upon the chip in which the correlation peaks. But an SPS receiver must also know when the satellite transmitted its code sequence to the SPS receiver.
An SPS satellite thus periodically transmits its time. For example, a GPS satellite transmits its time-of-week (TOW) every six seconds following a sub-frame preamble. In addition, the GPS satellite transmits its ephemeris or position in space. The TOW, ephemeris, and other data transmitted by the satellite are designated as “navigation data.” This navigation data is transmitted using a modulation overlay of navigation bits (“nav bits”) on the C/A code sequences. In particular, a group of C/A code sequences forms one nav bit.
To get the TOW, a GPS receiver must thus identify the sub-frame preamble. The preamble comprises eight nav bits. Once the sub-frame preamble is identified and the corresponding TOW decoded, a GPS receiver knows the transmission time for any C/A sequence in the sub-frame since each C/A code sequence is 1 millisecond in length. For example, if a GPS receiver correlates a C/A code sequence that is the 30th sequence after the preamble, the GPS receiver can determine that this code sequence's transmission time equals the TOW plus 30 milliseconds. But note that noise may have corrupted the nav bits such that the GPS receiver misidentifies the preamble. It is thus conventional for a GPS receiver to continue receiving and correlating the C/A sequences until it identifies the subsequent preamble. At that point, the probability of falsely identifying the sub-frame preamble is insignificant such that the receiver may proceed to obtain a position fix. Although this processing is conventional and well-understood, it requires the GPS receiver to be powered for at least six seconds until it receives the subsequent preamble and may proceed to obtain a first position fix. This six-second minimum time-to-first-fix is not an issue in, for example, automotive navigation applications in which there is abundant power available. But power consumption is very much an issue in mobile devices such as cellular telephones.
The reception of all the required navigation data upon a cold start for a GPS receiver can take up to 15 minutes. But the use of GPS technology in mobile devices such as cellular telephones has lead to the development of an assistance technique that is designated various ways in the industry such as by the term “extended ephemeris.” In extended ephemeris, a GPS receiver receives the navigation data through a second channel instead of needing to rely on the satellite's transmission of the navigation data. Through the use of extended ephemeris, a handset can immediately know which satellites are visible and what their ephemeris is. Extended ephemeris thus markedly reduces the time necessary to receive the navigation data. But even with extended ephemeris, the GPS receiver must still determine the satellite transmission time, which conventional requires six seconds as discussed above.
The navigation data may be better understood with reference to FIG. 1a, which illustrates how a navigational bit is a phase overlay on twenty consecutive C/A codes. At the navigation bit boundary, the phase overlay either flips (going from +1 to −1 or from −1 to +1) or stays the same. As will be discussed further herein, such a phase transition is problematic with regard to coherently integrating or summing the cross-correlations for a series of PRN sequences that extends over the navigation bit boundaries. As used herein a “PRN sequence” denotes the pseudorandom code transmitted by a navigation system satellite. For example, the PRN sequence for a GPS satellite comprises the 1024 chips for its C/A code. A sequence of PRN sequences that extends over the navigation bit boundaries thus comprise more than 20 C/A code sequences in a GPS embodiment. Coherently integrating across the navigation bit boundary must thus account for the navigation bit overlay. For example, if one navigation bit is +1 and the subsequent navigation bit is −1, the coherent integration of the cross-correlations for the PRN sequences for the first navigation bit is opposed by the coherent integration over the PEN sequences for a subsequent navigation bit. Regardless of the phase transition at each navigation bit boundary, the GPS navigation message is used in combination with the acquired pseudo ranging information from the C/A codes to complete the navigation equations to determine the location coordinates of the GPS receiver. The navigation bits themselves are divided into 25 frames, each having a length of 1500 bits (thus requiring an interval of 30 seconds for transmission in a GPS embodiment). FIG. 1b illustrates a frame of the complete signal. As shown in this figure, the HOW word repeats every six seconds at the start of a sub-frame subsequent to the TLM word. The HOW word includes the TOW discussed above.
To obtain a “pseudorange” to a given satellite, a GPS receiver correlates a copy of a satellite's unique pseudorandom (PRN) C/A sequence with the received PRN sequence. The copy is correlated with regard to each chip position. In other words, prior to acquiring the satellite signal, an SPS receiver does not know which chip position corresponds to the arrival time for the received PRN sequence. The pseudo-random nature of PRN sequence is quite advantageous in that received noise is effectively decorrelated by such a code. But if the copy of the PRN sequence is properly aligned with the received PRN sequence in a cross-correlation, all the chips coherently add together. This correlation peak occurs for one of the 1023 possible chip alignments of the received PRN sequence with the replica PRN sequence. The received PRN sequence is then located in time—its arrival time is known. But an SPS receiver must also search in frequency as well due to Doppler shift and local oscillator (LO) uncertainties. Once the received PRN sequence is located in time and frequency, the SPS receiver can obtain a “pseudorange” between it and the transmitting satellite. This pseudorange is based upon the time the satellite transmitted the PRN sequence and the time of reception by the SPS receiver. Based upon this elapsed time and the fact that the satellite transmission occurred at the speed of light, the SPS receiver can calculate the range between it and the transmitting satellite. But note that the satellite has a very accurate atomic clock. So there is relatively little uncertainty to the reported transmission time by the satellite. In contrast, the SPS receiver will typically have a relatively inexpensive clock, which is substantially less accurate than the satellite clock. The SPS receiver clock thus has an unknown offset to the satellite clock. For this reason, the time the SPS receiver believes it received the PRN sequence is not the ‘true” time that it would have calculated if it had a more accurate clock that was synchronized to the expensive satellite clock. This unknown clock offset adds uncertainty to the range measurement, hence it is denoted as a pseudorange.
Referring now to FIG. 2a, an SPS receiver knows the transmitting satellite's position in space from the associated ephemeris (whether that ephemeris was taken from the nav bits or was received in an extended ephemeris scheme). For example, the position of a satellite A 11 and a satellite B 12 is known. A pseudorange A 13 from satellite A forms a sphere about the satellite's position. If the SPS receiver were not earth-bound, it could be anywhere on the sphere. But if we assume that the SPS receiver is on the earth's surface, the pseudorange defined sphere intersects the earth's surface in a circular fashion as shown in FIG. 2a. A similar pseudorange-defined sphere about satellite B with regard to its pseudorange 14 produces another circular intersection. Since the SPS receiver is on the earth's surface (or if we assume so), it will then be located at the resulting intersection points 15 and 16, resulting in an ambiguous location. An SPS receiver thus needs more than just a pair of pseudoranges to get a position fix.
The clock offset uncertainty that affects location determination may be better understood with reference to FIG. 2b, which illustrates the result of the two acquired satellites SAT A 11 and SAT B 12 when the clock in SPS receiver 10 is 2 milliseconds late as compared to the clock of the SPS satellites. This causes the travel-time of the transmitted signals to appear to be 2 milliseconds longer than it actually is. The dotted ovals represent the actual range, Range_A 13 and Range_B 14, plus the range from the 2 ms clock offset. As the transmitted signals travel at the speed of light, even a small clock offset translates into large inaccuracies. Since atomic clocks are not a practical solution for SPS receivers, the problem is solved using an additional pseudorange.
FIG. 2c illustrate the intersections of a third pseudorange 22 with respect to a satellite C 21 with the pseudoranges from FIG. 2b. The pseudoranges all have the same clock offset because they are based they are based upon the same reception times in one SPS receiver. The three intersection points resulting from the three pseudoranges intersect at point 19, point 23 and point 24. From the intersection points, the clock offset is calculated by adjusting the clock offset until the three intersection points merge to a single point. Once this is completed, the clock of the SPS receiver has been synchronized with the atomic clock of the SPS satellite system. This is a 2-dimensional location as this point represents the intersection of the adjusted pseudoranges on the surface of the Earth. Additionally, acquiring a fourth concurrent satellite, resulting in a fourth concurrent pseudorange, will allow for a 3-dimensional location coordinate to be determined. Our attention now will switch to the process by which pseudoranges from individual satellites in the constellation are acquired, as it represents the most challenging aspect of obtaining the location coordinates of a GPS receiver. As described above, each SPS satellite broadcasts its unique identity via its particular PRN sequence (e.g., GPS uses a C/A code). The PRN sequence for each satellite is known by the SPS receiver, which compares it with the received composite signal. FIG. 3 shows a block diagram of a conventional SPS receiver. The composite signal from the SPS satellite constellation 30 is received by the RF front end 25, which down-converts the RF signal and converts it to a digital signal stream. The digital signal stream is input to the correlator block 26. Correlator block 26 correlates the incoming digital signal with the PRN sequence replica 29 stored in memory for each SPS satellite.
FIG. 4 illustrates how correlator 26 determines the receive time or arrival time of the signal from an SPS satellite by using the well-understood process of cross correlation. Even with a clear view of the sky, received signals are weak and all satellites broadcast over the same carrier frequency. Most SPS receivers implement multiple correlator blocks in parallel in order to acquire pseudoranges from multiple satellites simultaneously. For the purpose of this discussion, we will focus on the operation of a single correlator block. The composite digital signal that is received by the SPS receiver is input to a delay line made up of multiple delay elements. Corresponding chips (unit of the spreading code) from a PRN sequence replica 29 for the specific satellite that is being acquired are multiplied with the output of each delay element. The product of each delayed signal and chips from the PRN sequence replica 29 are summed and processed in a coordinate generator 28.
FIGS. 5 and 6 illustrates the correlator output of correlator 26 for different received signal powers. In FIG. 5, the received PRN sequence strength or SNR was such that correlator peaks representing the chip corresponding to the arrival time are greater than the noise floor, including peaks representing both white Gaussian noise as well as transmitted signal from a SPS satellite going through a multipath channel. This allows for the successful acquisition of the satellite. The received signal advances through the correlator delay line elements a chip at a time at the chip rate (1.023 MHz). The received PRN sequence will thus only align with the replica PRN sequence every n chips, where n is the number of chips in a complete PRN sequence. For example, n is 1023 in a GPS system such that the PRN sequence period is a millisecond. If the received signal is sufficiently powerful (it can actually be quite weak due to the power of coherently adding 1023 chips), a correlation peak occurs as shown in FIG. 5 that will repeat every 1 ms. This peak corresponds to the arrival time of a complete C/A code from the transmitting satellite, albeit with the clock offset uncertainty. The corresponding transmission time of the GPS signal is determined based on the time-stamp of the transmitted signal to determine the transmission delay, which is then converted according to the speed of light into a pseudorange in coordinate generator 28. When this information is acquired from four or more concurrent satellites, coordinate generator 28 employs the resulting navigational equations to determine the location coordinates of a GPS receiver (or three acquired concurrent satellites for a two-dimensional coordinate).
In practice, the process of cross correlation is much more involved. For example, movement of an SPS receiver relative to the individual satellites causes Doppler shifts. But more significantly, especially when the GPS receiver is located in a weak-signal environment such as indoor or urban canyon locations, path losses and signal multi-path significantly reduce the signal-to-noise ratio of the received signal, limiting the ability to successfully determine the signal travel-time distance and thus any ranging information between the satellite and the GPS receiver. In other words, the cross-correlation process would not yield any discernible peaks. FIG. 6 illustrates the correlator output in such a weak-signal environment. In this case, the correlator peaks are not distinguishable because they do not rise above the noise floor. Because the correlator peaks cannot be identified, it is not possible to determine the travel time necessary to determine the pseudorange information. There can be no position fix in such a weak-signal environment unless further processing is involved as discussed herein.
It is well known that increasing the signal-to-noise ratio via processing gain, and thus improving the ability to acquire the transmitted signals, can be achieved by coherently adding the cross-correlations for a series of PRN sequences. However, in practice, there are many significant technical challenges to increasing the processing gain and receive sensitivity by increasing the processing time. The gain from such coherent integration in conventional SPS receivers saturates at well under twenty PRN sequences (20 milliseconds in a GPS system). This explains the poor indoor and urban-canyon performance of current SPS receivers. There are a number of reasons that limit the coherent correlation times. First, as discussed above, the navigation data overlay such as the 50 Hz data overlay in a GPS system creates a structural boundary at every navigation symbol boundary (every 20-millisecond interval for GPS). As also mentioned earlier, the local clock used in SPS receivers is relatively inaccurate. When correlation times are increased, the clock drift during the length of the correlation period is large enough to degrade processing gain. In addition, all SPS satellite transmissions have a Doppler shift that depends upon their particular location in space relative to the SPS receiver. Moreover, if the SPS receiver is not stationary, its own motion compounds the satellite-motion-induced Doppler shift on the received satellite transmission. Another significant barrier is that SPS receivers are subject to low frequency fading, especially in indoor and urban-canyon locations. Low frequency fading refers to the variation of received signal strength from each satellite in the order of less than 10 Hz. This is due to the variation of signal blockers in line of sight of each of the satellites in the constellation. Movement of people and equipment also contribute to the variation of fading characteristics for each satellite signal. The signal fading significantly lowers the probability of the signals being acquired from a sufficient number of concurrent satellites to determine a position fix. Given these issues, the channel de-correlates both spatially and temporally.
A prior art example of an attempt to extend processing time beyond the navigation data symbol boundary such as the 50 Hz overlay boundary in GPS is described in Krasner (U.S. Pat. No. 6,016,119). Multiple correlator blocks are employed to process signals spanning multiple 50 Hz overlay boundaries. In order to account for the unknown values of the 50 Hz overlay signal, the output from each correlator block is squared, removing the sign. The squaring function removes the 50 Hz phase information, resulting in incoherent processing and significantly limiting the processing gain. As a consequence, this technique is not currently being practiced in commercially available products.
Accordingly, there is a need in the art for improved satellite-based position system (SPS) signal processing techniques in which the TTTF is improved using integration that extends over the navigation bit boundaries.